/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


 //自己实现的，冗杂版本的，不精致
 //题目需要分类讨论
// class Solution {
// public:
//     TreeNode* dfs_help(TreeNode* root, TreeNode* p, TreeNode* q) 
//     {
//         if(!root) return nullptr;
//         if(root==p||root==q) return root;
//         TreeNode* leftNode=dfs_help(root->left,p,q);
//         TreeNode* rightNode=dfs_help(root->right,p,q);
//         if(leftNode&&rightNode) return root;
//         else if(leftNode&&!rightNode) return leftNode;
//         else if(rightNode&&!leftNode) return rightNode;
//         else return nullptr;
//     }
//     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//         return dfs_help(root,p,q);
//     }
// };

//修改版
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(!root||root==p||root==q) return root;
       TreeNode* leftNode=lowestCommonAncestor(root->left,p,q);
       TreeNode* rightNode=lowestCommonAncestor(root->right,p,q);
       if(!leftNode) return rightNode;
       if(!rightNode) return leftNode;
       return root;
    }
};
